package algotithm.weekendrace.leetcode238.test2;

import java.util.Arrays;

/**
 * @author 25068
 * @Date 2021/4/25 10:29
 * @Title 5739. 最高频元素的频数
 */
public class Solution {

    public static void main(String[] args) {
        int[] nums = {1,2,4};
        int k = 5;
//        int[] nums = {9930,9923,9983,9997,9934,9952,9945,9914,9985,9982,9970,9932,9985,9902,9975,9990,9922,9990,9994,9937,9996,9964,9943,9963,9911,9925,9935,9945,9933,9916,9930,9938,10000,9916,9911,9959,9957,9907,9913,9916,9993,9930,9975,9924,9988,9923,9910,9925,9977,9981,9927,9930,9927,9925,9923,9904,9928,9928,9986,9903,9985,9954,9938,9911,9952,9974,9926,9920,9972,9983,9973,9917,9995,9973,9977,9947,9936,9975,9954,9932,9964,9972,9935,9946,9966};
//        int k = 3056;
        Solution solution = new Solution();
        int maxFrequency = solution.maxFrequency(nums, k);
        System.out.println(maxFrequency);
    }

    public int maxFrequency(int[] nums, int k) {
        int n = nums.length, ind = 0, max = 0;
        long[] pre = new long[n + 1];
        Arrays.sort(nums);
        for(int i = 0; i < n; i++) {
            while((long) (i - ind) * nums[i] - (pre[i] - pre[ind]) > k) {
                ind++;
            }
            //System.out.println(i + " " + ind + " " + max);
            max = Math.max(max, i - ind + 1);
            pre[i + 1] = pre[i] + nums[i];
        }
        //System.out.println(Arrays.toString(pre));
        return max;
    }
}
